def prime_factors(n):
    factors = {}
    #先分解2
    while n % 2 == 0:
        #字典中添加键值对，键为质因数，值为出现的次数
        factors[2] = factors.get(2, 0) + 1
        n = n // 2
    #分解奇数质因数
    i = 3
    #在分解质因数时，我们只需要检查到sqrt(n)就可以找到所有小于等于sqrt(n)的质因数
    while i * i <= n:
        while n % i == 0:
            factors[i] = factors.get(i, 0) + 1
            n = n // i
        i += 2
    #处理剩余质数
    if n > 2:
        factors[n] = 1
    return factors

n = 2024
factors = prime_factors(n)
factor_strings = []
for p, exp in factors.items():
    factor_strings.append(f"{p}^{exp}")
result = " × ".join(factor_strings)
print(f"{n} = {result}")

'''埃氏筛选法
not_prime = [0] * 4010  # 标记数组（0=素数，1=非素数）
prime = []
# 预处理4000以内的素数
for i in range(2, 4001):
    if not_prime[i] == 0:
        prime.append(i)
        # 标记倍数的方式，比直接试除法效率更高
        for j in range(2 * i, 4001, i):
            not_prime[j] = 1'''